# 输入两个链表，找出它们的第一个公共节点。
# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
# 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
# 输出：Reference of the node with value = 8


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        cur = headA
        length = 0
        while cur:
            length += 1
            cur = cur.next
        cur = headB
        while cur:
            length -= 1
            cur = cur.next
        cur = headA if length > 0 else headB
        cur1 = headB if cur == headA else headA
        length = abs(length)
        while length:
            cur = cur.next
            length -= 1
        while cur:
            if cur == cur1:
                return cur
            cur = cur.next
            cur1 = cur1.next
        return None


class Solution1:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A, B = headA, headB
        while A != B:
            A = A.next if A else headB
            B = B.next if B else headA
        return A
